package com.example.lettcode._202410._20241023;

import com.example.lettcode.node.ListNode;

import java.util.Deque;
import java.util.LinkedList;

/*
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1
 */
public class _1_shan_chu_lian_biao_n_ge_jie_dian {

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode list2 = new ListNode(2);
        ListNode list3 = new ListNode(3);
        ListNode list4 = new ListNode(4);
        ListNode list5 = new ListNode(5);
        list1.next = list2;
        list2.next = list3;
        list3.next = list4;
        list4.next = list5;
        ListNode listNode = removeNthFromEnd3(list1, 2);
        System.out.println(listNode);
    }

    /*
        暴力破解
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode tempNode1 = new ListNode(-1);
        tempNode1.next = head;
        int count = 0;
        ListNode tempNode2 = tempNode1;
        while (tempNode2 != null) {
            tempNode2 = tempNode2.next;
            count++;
        }

        ListNode tempNode3 = tempNode1;
        for (int i = 1; i <= count - n; i++) {
            if (i != (count - n)) {
                tempNode3 = tempNode3.next;
            } else {
                tempNode3.next = tempNode3.next.next;
            }
        }
        return tempNode1.next;
    }

    /*
        利用栈先进后出的特性，第n个出栈的就是要删除的
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        ListNode node = new ListNode(-1, head);
        Deque<ListNode> deque = new LinkedList<>();
        ListNode tempNode = node;
        while (tempNode != null) {
            deque.push(tempNode);
            tempNode = tempNode.next;
        }

        for (int i = 0; i < n; i++) {
            deque.pop();
        }
        ListNode listNode = deque.removeFirst();
        listNode.next = listNode.next.next;
        return node.next;
    }

    /*
        利用快慢指针，快指针比慢指针多走N步
     */
    public static ListNode removeNthFromEnd3(ListNode head, int n) {
        if (head == null) {
            return head;
        }

        ListNode node = new ListNode(-1, head);
        ListNode fastNode = node;
        ListNode slowNode = node;
        for (int i = 0; i <= n; i++) {
            fastNode = fastNode.next;
        }

        while (fastNode != null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }

        slowNode.next = slowNode.next.next;
        return node.next;
    }
}
